import functools


class Solution(object):
    def minCost(self, houses, cost, m, n, target):
        @functools.cache
        def dfs(i, j, k):
            if i == 0:
                if k == 1:
                    if houses[i] == 0:
                        return cost[i][j - 1]
                    else:
                        if houses[i] == j:
                            return 0
                        else:
                            return float('inf')
                else:
                    return float('inf')
            else:
                ans = float('inf')
                if houses[i]:
                    if houses[i] == j:
                        for last_val in range(1, n + 1):
                            if last_val == j:
                                ans = min(ans, dfs(i - 1, last_val, k))
                            else:
                                ans = min(ans, dfs(i - 1, last_val, k - 1))
                        return ans
                    else:
                        return float('inf')
                else:
                    for last_val in range(1, n + 1):
                        if last_val == j:
                            ans = min(ans, dfs(i - 1, last_val, k) + cost[i][j - 1])
                        else:
                            ans = min(ans, dfs(i - 1, last_val, k - 1) + cost[i][j - 1])
                    return ans
        ans = float('inf')
        for j in range(1, n + 1):
            ans = min(ans, dfs(m - 1, j, target))
        if ans < float('inf'):
            return ans
        else:
            return -1

data = Solution()
houses = [0, 0, 0, 0, 0]
cost = [[1, 10], [10, 1], [10, 1], [1, 10], [5, 1]]
m = 5
n = 2
target = 3
print(data.minCost(houses, cost, m, n, target))
